package greedy;

import java.util.Arrays;

/**
 * Created by lh on 2019/7/23.
 */
public class MaxSubArray {
    public static int maxSubArray(int[] nums) {
        if (nums == null && nums.length == 0) {
            return 0;
        }
        int sum = nums[0];
        int maxSum = sum;
        int indexStart = 0, indexEnd = 0;
        for (int i = 1; i < nums.length; i++) {
            if (sum <= 0) {
                indexStart = i;
            } else {
                indexEnd = i;
            }
            sum = sum > 0 ? sum + nums[i] : nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < maxSum) {
                indexEnd -= 1;
            }
        }
        System.out.println(Arrays.toString(Arrays.copyOfRange(nums, indexStart, indexEnd)));
        return maxSum;
    }
}
